Querying Large Graph Databases.
� Graph is a powerful modeling tool � Graph data is everywhere (e.g. chemistry, biology, image, vision, social networks, the Web, etc.)
GBLENDER towards blending visual query formulation and query processing in graph databases.

Finding maximal cliques in massive networks by H%2A%2Dgraph.
Maximal clique enumeration (MCE) is a fundamental problem in graph theory and has important applications in many areas such as social network analysis and bioinformatics. The problem is extensively studied; however, the best existing algorithms require memory space linear in the size of the input graph. This has become a serious concern in view of the massive volume of today’s fastgrowing network graphs. Since MCE requires random access to different parts of a large graph, it is difficult to divide the graph into smaller parts and process one part at a time, because either the result may be incorrect and incomplete, or it incurs huge cost on merging the results from different parts. We propose a novel notion, H ∗-graph, which defines the core of a network and extends to encompass the neighborhood of the core for MCE computation. We propose the first external-memory algorithm for MCE (ExtMCE) that uses theH ∗-graph to bound the memory usage. We prove both the correctness and completeness of the result computed by ExtMCE. Extensive experiments verify that ExtMCE efficiently processes large networks that cannot be fit in the memory. We also show that the H ∗-graph captures important properties of the network; thus, updating the maximal cliques in the H ∗-graph retains the most essential information, with a low update cost, when it is infeasible to perform update on the entire network.
K%2Disomorphism privacy preserving network publication against structural attacks.

Efficient processing of group%2Doriented connection queries in a large graph.

Context%2DAware Object Connection Discovery in Large Graphs.

Efficient Discovery of Frequent Correlated Subgraph Pairs.
The recent proliferation of graph data in a wide spectrum of applications has led to an increasing demand for advanced data analysis techniques. In view of this, many graph mining techniques, such as frequent subgraph mining and correlated subgraph mining, have been proposed. In many applications, both frequency and correlation play an important role. Thus, this paper studies a new problem of mining the set of frequent correlated subgraph pairs. A simple algorithm that combines existing algorithms for mining frequent subgraphs and correlated subgraphs results in a multiplication of the mining operations, the majority of which are redundant. We discover that most of the graphs correlated to a common graph are also highly correlated. We establish theoretical foundations for this finding and derive a tight lower bound on the correlation of any two graphs that are correlated to a common graph. This theoretical result leads to the design of a very effective skipping mechanism, by which we skip the processing of a majority of graphs in the mining process. Our algorithm, FCP-Miner, is a fast approximate algorithm, but we show that the missing pairs are only a small set of marginally correlated pairs. Extensive experiments verify both the efficiency and effectiveness of FCP-Miner.
Top%2Dk Correlative Graph Mining.

Efficient query processing on graph databases.

Correlated pattern mining in quantitative databases.

Effective elimination of redundant association rules.

Efficient Correlation Search from Graph Databases.

Maintaining frequent closed itemsets over a sliding window.
Abstract. In this paper, we study the incremental update of Frequent Closed Itemsets (FCIs) over a sliding window in a high-speed data stream. We propose the notion of semi-FCIs, which is to progressively increase the minimum support threshold for an itemset as it is retained longer in the window, thereby drastically reducing the number of itemsets that need to be maintained and processed. We explore the properties of semi-FCIs and observe that a majority of the subsets of a semi-FCI are not semi-FCIs and need not be updated. This finding allows us to devise an efficient algorithm, IncMine, that incrementally updates the set of semi-FCIs over a sliding window. We also develop an inverted index to facilitate the update process. Our empirical results show that IncMine achieves significantly higher throughput and consumes less memory than the state-of-the-art streaming algorithms for mining FCIs and FIs. IncMine also attains high accuracy of 100 % precision and over 93 % recall. 1
An information%2Dtheoretic approach to quantitative association rule mining.
Abstract. Quantitative Association Rule (QAR) mining has been rec-ognized an influential research problem over the last decade due to the popularity of quantitative databases and the usefulness of associ-ation rules in real life. Unlike Boolean Association Rules (BARs), which only consider boolean attributes, QARs consist of quantitative attributes which contain much richer information than the boolean attributes. How-ever, the combination of these quantitative attributes and their value in-tervals always gives rise to the generation of an explosively large number of itemsets, thereby severely degrading the mining efficiency. In this paper, we propose an information-theoretic approach to avoid un-rewarding combinations of both the attributes and their value intervals being generated in the mining process. We study the mutual information between the attributes in a quantitative database and devise a normal-ization on the mutual information to make it applicable in the context of QAR mining. To indicate the strong informative relationships among the
A survey on algorithms for mining frequent itemsets over data streams.
The increasing prominence of data streams arising in a wide range of advanced applications such as fraud detection and trend learning has led to the study of online mining of frequent itemsets (FIs). Unlike mining static databases, mining data streams poses many new challenges. In addition to the one-scan nature, the unbounded memory requirement and the high data arrival rate of data streams, the combinatorial explosion of itemsets exacerbates the mining task. The high complexity of the FI mining problem hinders the application of the stream mining techniques. We recognize that a critical review of existing techniques is needed in order to design and develop efficient mining algorithms and data structures that are able to match the processing rate of the mining with the high arrival rate of data streams. Within a unifying set of notations and terminologies, we describe in this paper the efforts and main techniques for mining data streams and present a compre-hensive survey of a number of the state-of-the-art algorithms on mining frequent itemsets over data streams. We classify the stream-mining techniques into two categories based on the window model that they adopt in order to provide in-sights into how and why the techniques are useful. Then, we further analyze the algorithms according to whether they are exact or approximate and, for approxi-mate approaches, whether they are false-positive or false-negative. We also discuss various interesting issues, including the merits and limitations in existing research and substantive areas for future research. 1 1
An information%2Dtheoretic approach to quantitative association rule mining.
Abstract. Quantitative Association Rule (QAR) mining has been rec-ognized an influential research problem over the last decade due to the popularity of quantitative databases and the usefulness of associ-ation rules in real life. Unlike Boolean Association Rules (BARs), which only consider boolean attributes, QARs consist of quantitative attributes which contain much richer information than the boolean attributes. How-ever, the combination of these quantitative attributes and their value in-tervals always gives rise to the generation of an explosively large number of itemsets, thereby severely degrading the mining efficiency. In this paper, we propose an information-theoretic approach to avoid un-rewarding combinations of both the attributes and their value intervals being generated in the mining process. We study the mutual information between the attributes in a quantitative database and devise a normal-ization on the mutual information to make it applicable in the context of QAR mining. To indicate the strong informative relationships among the
An Efficient Index Lattice for XML Query Evaluation.

A Development of Hash%2DLookup Trees to Support Querying Streaming XML.

Mining Vague Association Rules.
Abstract. In many online shopping applications, traditional Association Rule (AR) mining has limitations as it only deals with the items that are sold but ignores the items that are almost sold. For example, those items that are put into the basket but not checked out. We say that those almost sold items carry hesitation information since customers are hesitating to buy them. The hesitation information of items is valuable knowledge for the design of good selling strategies. We apply vague set theory in the context of AR mining as to incorporate the hesitation information into the ARs. We define the concepts of attractiveness and hesitation of an item, which represent the overall information of a customer’s intent on an item. Based on these two concepts, we propose the notion of Vague Association Rules (VARs) and devise an efficient algorithm to mine the VARs. Our experiments show that our algorithm is efficient and the VARs capture more specific and richer information than traditional ARs. 1
Correlation search in graph databases.
Correlation mining has gained great success in many application domains for its ability to capture the underlying dependency between objects. However, the research of correlation mining from graph databases is still lacking despite the fact that graph data, especially in various scientific domains, proliferate in recent years. In this paper, we propose a new problem of correlation mining from graph databases, called Correlated Graph Search (CGS). CGS adopts Pearson’s correlation coefficient as a correlation measure to take into consideration the occurrence distributions of graphs. However, the problem poses significant challenges, since every subgraph of a graph in the database is a candidate but the number of subgraphs is exponential. We derive two necessary conditions which set bounds on the occurrence probability of a candidate in the database. With this result, we design an efficient algorithm that operates on a much smaller projected database and thus we are able to obtain a significantly smaller set of candidates. To further improve the efficiency, we develop three heuristic rules and apply them on the candidate set to further reduce the search space. Our extensive experiments demonstrate the effectiveness of our method on candidate reduction. The results also justify the efficiency of our algorithm in mining correlations from large real and synthetic datasets.
Fg%2Dindex towards verification%2Dfree query processing on graph databases.

An Efficient Approach to Support Querying Secure Outsourced XML Information.
Abstract. Data security is well-recognized a vital issue in an information system that is supported in an outsource environment. However, most of conventional XML encryption proposals treat confidential parts of an XML document as whole blocks of text and apply encryption algorithms directly on them. As a result, queries involving the encrypted part cannot be efficiently processed. In order to address these problems, we propose XQEnc, a novel approach to support querying encrypted XML. XQEnc is based on two important techniques of vectorization and skeleton compression. Essentially, vectorization, which is a generalization of columns of a relational table, makes use the basic path of an XML tree to label the data values. Skeleton compression collapses the redundant paths into a multiplicity attribute. Our analysis and experimental study shows that XQEnc achieves both better query efficiency and more robust security compared with conventional methods. As an application, we show how XQEnc can be realized with relational techniques to enable secure XML data outsourcing. 1
MIC Framework An Information%2DTheoretic Approach to Quantitative Association Rule Mining.

delta%2DTolerance Closed Frequent Itemsets.

Mining quantitative correlated patterns using an information%2Dtheoretic approach.
Existing research on mining quantitative databases mainly focuses on mining associations. However, mining associations is too expensive to be practical in many cases. In this paper, we study mining correlations from quantitative databases and show that it is a more effective approach than mining associations. We propose a new notion of Quantitative Correlated Patterns (QCPs), which is founded on two formal concepts, mutual information and all-confidence. We first devise a normalization on mutual information and apply it to QCP mining to capture the dependency between the attributes. We further adopt all-confidence as a quality measure to control, at a finer granularity, the dependency between the attributes with specific quantitative intervals. We also propose a supervised method to combine the consecutive intervals of the quantitative attributes based on mutual information, such that the interval combining is guided by the dependency between the attributes. We develop an algorithm, QCoMine, to efficiently mine QCPs by utilizing normalized mutual information and all-confidence to perform a two-level pruning. Our experiments verify the efficiency of QCoMine and the quality of the QCPs.
Maintaining Frequent Itemsets over High%2DSpeed Data Streams.
Abstract. We propose a false-negative approach to approximate the set of frequent itemsets (FIs) over a sliding window. Existing approximate algorithms use an error parameter, ǫ, to control the accuracy of the mining result. However, the use of ǫ leads to a dilemma. A smaller ǫ gives a more accurate mining result but higher computational complexity, while increasing ǫ degrades the mining accuracy. We address this dilemma by introducing a progressively increasing minimum support function. When an itemset is retained in the window longer, we require its minimum support to approach the minimum support of an FI. Thus, the number of potential FIs to be maintained is greatly reduced. Our experiments show that our algorithm not only attains highly accurate mining results, but also runs significantly faster and consumes less memory than do existing algorithms for mining FIs over a sliding window. 1
XQzip Querying Compressed XML Using Structural Indexing.
Abstract. XML makes data flexible in representation and easily portable on the Web but it also substantially inflates data size as a consequence of using tags to describe data. Although many effective XML compressors, such as XMill, have been recently proposed to solve this data inflation problem, they do not address the problem of running queries on compressed XML data. More recently, some compressors have been proposed to query compressed XML data. However, the compression ratio of these compressors is usually worse than that of XMill and that of the generic compressor gzip, while their query performance and the expressive power of the query language they support are inadequate. In this paper, we propose XQzip, an XML compressor which supports querying compressed XML data by imposing an indexing structure, which we call Structure Index Tree (SIT), on XML data. XQzip addresses both the compression and query performance problems of existing XML compressors. We evaluate XQzip’s performance extensively on a wide spectrum of benchmark XML data sources. On average, XQzip is able to achieve a compression ratio 16.7 % better and a querying time 12.84 times less than another known queriable XML compressor. In addition, XQzip supports a wide scope of XPath queries such as multiple, deeply nested predicates and aggregation. 1
Comparative Analysis of XML Compression Technologies.

XQzip Querying Compressed XML Using Structural Indexing.
Abstract. XML makes data flexible in representation and easily portable on the Web but it also substantially inflates data size as a consequence of using tags to describe data. Although many effective XML compressors, such as XMill, have been recently proposed to solve this data inflation problem, they do not address the problem of running queries on compressed XML data. More recently, some compressors have been proposed to query compressed XML data. However, the compression ratio of these compressors is usually worse than that of XMill and that of the generic compressor gzip, while their query performance and the expressive power of the query language they support are inadequate. In this paper, we propose XQzip, an XML compressor which supports querying compressed XML data by imposing an indexing structure, which we call Structure Index Tree (SIT), on XML data. XQzip addresses both the compression and query performance problems of existing XML compressors. We evaluate XQzip’s performance extensively on a wide spectrum of benchmark XML data sources. On average, XQzip is able to achieve a compression ratio 16.7 % better and a querying time 12.84 times less than another known queriable XML compressor. In addition, XQzip supports a wide scope of XPath queries such as multiple, deeply nested predicates and aggregation. 1
